#include <iostream>
#include <fstream>
#include <cmath>
#include <ctime>
#include <climits>
#include <windows.h>
using namespace std;


// QUESTOES (algoritmos principais)
int Questao5(int* vetor, int p, int r);
int Questao6(int* vetor1, int* vetor2, int p1, int r1, int p2, int r2);
void Questao7(int* vetor, int n, int x);
int Questao8(int* vetor, int p, int r);
void Questao10(int* vetor, int p, int r, int pivo);
int Questao12(int* vetor, int N, double prob);
void Questao13(double* vetor, int N, int K, double relax);

// algoritmos auxiliares
void HeapSort(int* vetor, int p, int r);
void InsertionSort(int* vetor, int p, int r);
void CountingSort(double* A, int N, int K);
int Busca_Binaria(int* vetor, int elemento, int p, int r);
int Selecao(int* A, int p, int r, int k);
void imprimir_vetor(int* vetor, int N, string filename);
void imprimir_vetor2(double* vetor, int N, string filename);

// -------------------------------------------------------------
// --- MAIN ----------------------------------------------------
// -------------------------------------------------------------
int main() {

	int i;
	// ----------------------------
	// --- QUESTAO 5 --------------
	// ----------------------------
	cout<<endl;
	int N = 1001; //N=1000;
	int* vetor5 = new int [N];
	for (i=0; i<N; i++) vetor5[i] = 11 + i%2;
	int maj = Questao5(vetor5,0,N-1);
	if (maj<0) cout<<"<Questao5> NAO tem majoritario"<<endl;
	else cout<<"<Questao5> Tem majoritario = "<<maj<<endl;
	delete [] vetor5;

	// ----------------------------
	// --- QUESTAO 6 --------------
	// ----------------------------
	cout<<endl;
	N = 16;
	int* vetor6a = new int [N];
	int* vetor6b = new int [N];
	for (i=0; i<N; i++) vetor6a[i] = i;
	for (i=0; i<N; i++) vetor6b[i] = 2*i;
	//HeapSort(vetor6a,0,N-1); HeapSort(vetor6b,0,N-1);
	imprimir_vetor(vetor6a, N, "entrada_questao6a.txt");
	imprimir_vetor(vetor6b, N, "entrada_questao6b.txt");

	int med = Questao6(vetor6a,vetor6b,0,N-1,0,N-1);
	cout<<"<Questao6> Mediana de X1 e X2 ordenados: = "<<med<<endl;

	// ----------------------------
	// --- QUESTAO 7 --------------
	// ----------------------------
	cout<<endl;
	N = 250000;
	int* vetor7 = new int [N];
	for (i=0; i<N; i++) vetor7[i] = 0;
	vetor7[10000] = 4999;
	vetor7[20000] = 5001;
	Questao7(vetor7, N, 10000);
	Questao7(vetor7, N, 10001);
	delete [] vetor7;

	// ----------------------------
	// --- QUESTAO 8 --------------
	// ----------------------------
	cout<<endl;
	N = 1000;
	int* vetor8 = new int [N];
	for (i=0; i<N; i++) if (i%2==0) vetor8[i] = i; else vetor8[i]=i-2;

	int inv = Questao8(vetor8,0,N-1);
	cout<<"<Questao8> Numero de inversoes = "<<inv<<endl;
	delete [] vetor8;

	// ----------------------------
	// --- QUESTAO 10 -------------
	// ----------------------------
	cout<<endl;
	N = 100;
	int* vetor10 = new int [N];
	for (i=0; i<N; i++) vetor10[i] = 5*(i/5);
	imprimir_vetor(vetor10, N, "entrada_questao10.txt");
	Questao10(vetor10,0,N-1,10);
	delete [] vetor10;

	// ----------------------------
	// --- QUESTAO 12 -------------
	// ----------------------------
	cout<<endl;
	N = 1000; //N=1002;
	double prob = 1.0/3;
	int* vetor12 = new int [N];
	for (i=0; i<N; i++) vetor12[i] = 11 + i%3;
	int pop = Questao12(vetor12, N, prob);
	if (pop<0) cout<<"<Questao12> NAO tem popular"<<endl;
	else cout<<"<Questao12> Tem popular = "<<pop<<endl;
	delete [] vetor12;

	// ----------------------------
	// --- QUESTAO 13 -------------
	// ----------------------------
	cout<<endl;
	N = 1000;
	int K=100;
	double* vetor13 = new double [N];
	for (i=0; i<N; i++) vetor13[i] = (double) K * rand()/RAND_MAX;
	double relax = 0.1; // A[i]<A[i+1]+relax //relax > 0
	Questao13(vetor13, N, K, relax);
	imprimir_vetor2(vetor13, N, "saida_questao13.txt");
	delete [] vetor13;
	cout<<"<Questao13> ver arquivo saida_questao13.txt"<<endl;

	return 0;
}


// ------------------------------------------------------------------------------------------------
// ---- QUESTOES (algoritmos principais) ----------------------------------------------------------
// ------------------------------------------------------------------------------------------------


// ------------------------------------------------
// ---- QUESTAO 5 ---------------------------------
// ------------------------------------------------
int Conta(int* vetor, int p, int r, int elemento) {
    int cont = 0;
    for (int i=p; i<=r; i++) {
        if (vetor[i]==elemento) cont++;
    }
    return cont;
}

int Questao5(int* vetor, int p, int r) {
    if (p==r) return vetor[p];
    int q = (p+r)/2;
    int x1 = Questao5(vetor,p,q);
    int x2 = Questao5(vetor,q+1,r);

    int N1=-1; int N2=-1;
    if (x1>=0) N1 = Conta(vetor,p,r,x1);
    if (x2>=0) N2 = Conta(vetor,p,r,x2);
    if (N1 > (r-p+1)/2) return x1;
    if (N2 > (r-p+1)/2) return x2;
    return -1;
}

// ---------------------------------------------------------------------
// ---- QUESTAO 6 ------------------------------------------------------
// ---------------------------------------------------------------------
int Questao6(int* vetor1, int* vetor2, int p1, int r1, int p2, int r2) {
    if ((r1-p1<=1)&&(r2-p2<=1)) {
        int n = r1-p1+1 + r2-p2+1;
        int* aux = new int[n];
        int j=0;
        for (int i=p1; i<=r1; i++) aux[j++] = vetor1[i];
        for (int i=p2; i<=r2; i++) aux[j++] = vetor2[i];
        InsertionSort(aux,0,n-1);
        int med = aux[n/2];
        delete[] aux;
        return med;
    }

    int q1 = (p1+r1)/2;
    int q2 = (p2+r2)/2;
    int med1 = vetor1[q1];
    int med2 = vetor2[q2];

    if (med1==med2) return med1;
    if (med1<med2)
        return Questao6(vetor1, vetor2,q1,r1,p2,q2);
    else
        return Questao6(vetor1, vetor2,p1,q1,q2,r2);
}

// ------------------------------------------
// ---- QUESTAO 7 ---------------------------
// ------------------------------------------
void Questao7(int* vetor, int n, int x) {
    HeapSort(vetor,0,n-1);
    int i, q=-1;
    for (i=0; i<n; i++) {
        q = Busca_Binaria(vetor, x-vetor[i], 0, n-1);
        if (q>=0) break;
    }
    if (q<0) cout<<"<Questao7> NAO existem elementos com soma = "<<x<<endl;
    else cout<<"<Questao7> Existem os elementos: "<<vetor[i]<<"+"<<vetor[q]<<" = "<<x<<endl;
}

// ----------------------------------------------------
// ---- QUESTAO 8 ------------------------------------
// ----------------------------------------------------
int Merge_cont(int* vetor, int p, int q, int r) {
    int infinito = INT_MAX;
    int N1 = q-p+1;
    int N2 = r-q;
    int* esq = new int [N1+1];
    int* dir = new int[N2+1];
    for (int i=0; i<N1; i++) esq[i]=vetor[p+i];
    for (int j=0; j<N2; j++) dir[j]=vetor[q+j+1];
    esq[N1] = infinito;
    dir[N2] = infinito;

    int i=0; int j=0;
    int cont = 0;
    for (int k=p; k<=r; k++) {
        if (esq[i]<=dir[j]) {
            vetor[k] = esq[i++];
            cont += j;
        } else {
            vetor[k] = dir[j++];
        }
    }
    delete[] esq;
    delete[] dir;
    return cont;
}

int Questao8(int* vetor, int p, int r) {
    if (p>=r) return 0;
    int q = (p+r)/2;
    int cont1 = Questao8(vetor,p,q);
    int cont2 = Questao8(vetor,q+1,r);
    int cont3 = Merge_cont(vetor,p,q,r);
    return cont1 + cont2 + cont3;
}

// ------------------------------------------------
// ---- QUESTAO 10 --------------------------------
// ------------------------------------------------
void trocar(int& x, int& y) {int z = x; x = y; y = z;}

void Questao10(int* vetor, int p, int r, int pivo) {
    int i=p-1;
    int j=p-1;
    for (int k=p; k<=r; k++) {
        if (vetor[k] < pivo) {
            i++; j++;
            trocar(vetor[i], vetor[k]);
            trocar(vetor[k], vetor[j]);
        } else if (vetor[k]==pivo) {
            j++;
            trocar(vetor[j], vetor[k]);
        }
    }
    cout<<"<Questao10> q1="<<i<<"; q2="<<j<<endl;
}

// ----------------------------------------------------
// ---- QUESTAO 12 ------------------------------------
// ----------------------------------------------------
int Questao12(int* vetor, int N, double prob) {
    int k = ceil(1.0/prob);
    for (int i=1; i<k; i++) {
        int candidato = Selecao(vetor,0,N-1,i*N/k);
        int cont = Conta(vetor, 0, N-1, candidato);
        if (cont>prob*N) return candidato;
    }
    return -1;
}

// --------------------------------------------------------
// ---- QUESTAO 13 ----------------------------------------
// --------------------------------------------------------
void Questao13(double* vetor, int N, int K, double relax) {
    for (int i=0; i<N; i++) vetor[i] /= relax;
    K /= relax;
    CountingSort(vetor, N, K);
    for (int i=0; i<N; i++) vetor[i] *= relax;
}


// ------------------------------------------------------------------------------------------------
// ---- ALGORITMOS AUXILIARES ---------------------------------------------------------------------
// ------------------------------------------------------------------------------------------------



// --- INSERTION_SORT ------------------------
void InsertionSort(int* vetor, int p, int r) {
    int i,j,carta;
    for (j=p+1;j<=r;j++) {
        carta = vetor[j];
        i = j-1;
        while ((i>=p)&&(vetor[i]>carta)) {
            vetor[i+1] = vetor[i];
            i--;
        }
        vetor[i+1] = carta;
    }
}

// --- HEAP_SORT -------------------------------------
void maxheapify(int* vetor, int i, int p, int r) {
    int m = i;
    int esq = p+2*(i-p)+1;
    int dir = p+2*(i-p)+2;
    if ((esq<=r)&&(vetor[esq]>vetor[i])) m = esq;
    if ((dir<=r)&&(vetor[dir]>vetor[m])) m = dir;
    if (m != i) {
        trocar(vetor[i], vetor[m]);
        maxheapify(vetor,m,p,r);
    }
}

void HeapSort(int* vetor, int p, int r) {
    int i;
    for (i=(r+p-1)/2; i>=p; i--) {
        maxheapify(vetor,i,p,r);
    }
    for (i=r;i>p;i--) {
        trocar(vetor[p], vetor[i]);
        r = r-1;
        maxheapify(vetor,p,p,r);
    }
}

// --- Busca_Binaria --------------------------------------
int Busca_Binaria(int* vetor, int elemento, int p, int r) {
    while (p<=r) {
        int q = (p+r)/2;
        if (vetor[q]< elemento) p = q+1; else
        if (vetor[q]> elemento) r = q-1; else
        if (vetor[q]==elemento) return q;
    }
    return -1;
}

// --- Algoritmo PARTICIONE ------------------------
int Particione(int* vetor, int p, int r, int pivo) {
    int j, i=p-1;
    for (j=p; j<r; j++) {
        if (vetor[j] < pivo) {
            i++;
            trocar(vetor[i], vetor[j]);
        } else if (vetor[j]==pivo) {
            trocar(vetor[j], vetor[r]);
            break;
        }
    }
    for (j=j; j<r; j++) {
        if (vetor[j] <= pivo) {
            i++;
            trocar(vetor[i], vetor[j]);
        }
    }
    trocar(vetor[i+1], vetor[r]);
    return i+1;
}

// --- Algoritmo SELECAO -----------------
int Selecao(int* A, int p, int r, int k) {
    int i, N=r-p+1;
    if (N<10) {
        if (k>N) k=N;
        InsertionSort(A,p,r);
        return A[p+k-1];
    }
    int tam_M = N/5;
    int* M = new int[tam_M];
    for (i=0; i<tam_M; i++) {
        InsertionSort(A, p+5*i, p+5*i+4);
        M[i] = A[p+5*i+2];
    }
    int pivo = Selecao(M, 0, tam_M-1, tam_M/2);
    delete[] M;
    int q = Particione(A, p, r, pivo);
    i = q-p+1;
    if (k==i) return A[q];
    if (k<i) return Selecao(A,p,q-1,k);
    return Selecao(A,q+1,r,k-i);
}

// ---- COUNTING-SORT --------------------------------
void CountingSort(double* A, int N, int K) {
    int i,j;
    double* B = new double[N];
    int* C = new int[K+1];
    for (i=0; i<=K; i++) C[i] = 0;
    for (j=0; j<N; j++) C[(int)A[j]]++;
    for (i=1; i<=K; i++) C[i] = C[i]+C[i-1];
    for (j=N-1; j>=0; j--) B[--C[(int)A[j]]] = A[j];
    for (j=0; j<N; j++) A[j] = B[j];
    delete[] B;
    delete[] C;
}


// --- Imprimir vetor em arquivo ------------------------
void imprimir_vetor(int* vetor, int N, string filename) {
    if (filename=="") filename="saida.txt";
    ofstream arq;
    arq.open(filename.c_str());
    for (int i=0;i<N;i++) arq<<vetor[i]<<" ";
    arq.close();
}

// --- Imprimir vetor em arquivo ------------------------
void imprimir_vetor2(double* vetor, int N, string filename) {
    if (filename=="") filename="saida.txt";
    ofstream arq;
    arq.open(filename.c_str());
    for (int i=0;i<N;i++) arq<<vetor[i]<<" ";
    arq.close();
}